#ifndef	_NESTER_H_
#define	_NESTER_H_

#include <vector>
#include <queue>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <string>
//debug
#include <glut_viewer/glut_viewer.h>

#include <Geex/basics/types.h>
#include <Geex/basics/assert.h>
#include "containers.h"
#include "polytope.h"
#include "bin_packing.h"
#include "overlap.h"

namespace Nesting 
{

	using namespace Geex;
	class Nesting_graphics;

	class Nester 
	{
		
		friend class Nesting_graphics;
		typedef Overlap_2::Vector_2 Vector_2;

	public:
		
		Nester(const std::string& tile_filename) ;
		~Nester();
		/* 
		** set methods 
		*/
		void shrink_bdbox(double f);
		/* 
		** query methods 
		*/
		static Nester* instance() { return instance_ ; }

		/* 
		** debug 
		*/
		
		/* 
		** computation 
		*/
		void find_nonoverlap_pos(); // every polytope is considered
		//double find_nonoverlap_pos( unsigned int index, const Overlap_2::Vector_2& v ); // polytope with index is considered
		void guided_local_search(unsigned int index);
		// distribute all the polytopes
		void initially_place(); 
		/* 
		** miscellaneous 
		*/
		void get_bbox(real& x_min, real& y_min, real& z_min, real& x_max, real& y_max, real& z_max);
	private:
		double local_search(unsigned int idx, 
							const Overlap_2::Vector_2& v, 
							//double pre_obj_val,
							//double& obj_val,
							//double scale,
							const std::vector< std::vector<double> >& penalties, 
							std::vector< std::vector<double> >& miu,
							std::vector<unsigned int>& overlap_with,
							Nesting_polygon& res) ;
	private:
		static Nester* instance_ ;

		// container
		Container_box *cbox;

		// polygons to be packed
		std::vector<Nesting_polytope*> polytope_set;
		double total_volume; // total area of all polygons
		double max_volume;

		struct area_cmp : std::binary_function<Nesting_polytope*, Nesting_polytope*, bool>
		{
			bool operator()(const Nesting_polytope* p0, const Nesting_polytope* p1) const
			{
				return p0->volume() < p1->volume();
			}
		};
		struct width_cmp : std::binary_function<Nesting_polygon*, Nesting_polygon*, bool>
		{
			bool operator()(const Nesting_polygon* p0, const Nesting_polygon* p1) const
			{
				typedef CGAL::Iso_rectangle_2<K> Iso_rectangle_2;
				Iso_rectangle_2 bdbox0 = p0->bbox(), bdbox1 = p1->bbox();
				double width0 = bdbox0.xmax() - bdbox0.xmin();
				double width1 = bdbox1.xmax() - bdbox1.xmin();
				return width0 < width1;
			}
		};

	} ;


}

#endif